Generate parentheses

Time: O(4N/N(3/2)); Space: O(N); medium

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3

Output:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Example 2:

Input: n = 2

Output:

[
  "()()",
  "(())"
]

[6]:

class Solution1(object):
    """
    Time: O(4^N/N^(3/2))~=CatalanNumbers
    Space: O(N)
    """
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        result = []
        self.generateParenthesisRecu(result, '', n, n)
        return result

    def generateParenthesisRecu(self, result, current, left, right):
        if left == 0 and right == 0:
            result.append(current)
        if left > 0:
            self.generateParenthesisRecu(result, current + "(", left - 1, right)
        if left < right:
            self.generateParenthesisRecu(result, current + ")", left, right - 1)

[7]:

s = Solution1()

n = 3
assert s.generateParenthesis(n) == [
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

n = 2
assert s.generateParenthesis(n) == ["()()","(())"] or ['(())', '()()']